In binary computing devices hardware direct lookup tables are typically employed for function evaluation and for reciprocal and root reciprocal seed values for division and square root procedures. For direct table lookup of a function of a normalized “p-bit” argument 1≦x=1.b1b2 . . . bibi+1 . . . bp−1<2, the “i” leading bits b1 b2 . . . bi provide an index to a table yielding “j” output bits that determine the approximate function value.
Two major disadvantages of prior art hardware direct lookup tables are:
(1) A prior art hardware direct lookup table generally contains considerable repetition of common leading portions of output values. This results in the table being considered prohibitively large for certain applications, particularly when the application requires the number of input bits “i” to be equal or greater than the number of output bits “j”.
(2) For direct lookup of functions that change slowly in some portions of the argument domain and then change very rapidly in other portions of the argument domain, the effective accuracy and amount of output digit repetition that is generated varies considerably over the range of output values.
To provide greater function accuracy and to avoid an excessive size of a comparable direct lookup table, certain types of prior art table lookup systems employing multiple table lookups and arithmetic combining operations have been devised. These table lookup systems include bipartite tables such as those described in U.S. Pat. No. 5,862,059. Another type of table lookup system uses exponential/logarithm tables such as those described in U.S. Pat. No. 5,197,024. Other types of table lookup systems are based on well known multiplicative interpolation systems.
Some of the disadvantages of these prior art types of hardware table lookup systems for function approximation include:
(1) The table lookups and related computations can require several cycles of latency on the critical path of the overall function evaluation procedure.
(2) The table lookup system can require supplemental dedicated hardware to effect the implicit table size reduction, and
(3) A table lookup assisted computation generally provides alternative approximate function values differing from those of a comparably accurate direct table lookup. Therefore the table lookup assisted computation procedure is a “lossy compression” procedure.
It should be recognized that even though a lookup table provides approximate values, there are many reasons why table compression should still be a lossless compression rather than just a methodology to provide values of roughly the same accuracy as the initial direct lookup table values. These reasons include the issues of adherence to standards, the maintenance of legacy systems behavior, and the facility for reproducible behavior for verification and testing.
A prior art direct table lookup procedure that incorporates lossless compression techniques to avoid excessive repetition of common leading digits of successive output values enumerated in the table is a low order digit accuracy refinement method used in published decimal lookup tables for function approximation. For example, consider a decimal logarithm table of the type printed in the book “Mathematical Tables from the Handbook of Chemistry and Physics” published for many years by the Chemical Rubber Publishing Company of Cleveland, Ohio.
A published lookup table such as a five (5) digit index decimal logarithm table is an example of a decimal based direct lookup table. Each decimal input value indexes an output with a corresponding number of output decimal digits (plus perhaps a fixed number of extra guard digits to provide more output accuracy). Thus the five (5) digit input value N=11502 can index an eight (8) digit output value 4.0607734. The output value 4.0607734 is the rounded decimal logarithm of the input value N=11502. Similarly, the five (5) digit input value N=11509 can index the output value 4.0610376. The output value 4.0610376 is the rounded decimal logarithm of the input value N=11509. Table compression in the printed table may be obtained by employing the low order decimal input index digit as a refined value selector.
For purposes of explaining the concept of table compression the input index can be partitioned into high and low order indices. Let the expression 4|1 denote an “input partition” with one low order refinement digit. The digit “4” in the expression 4|1 denotes four (4) high order digits that index a line of the table where the outputs are given in a partitioned form. The digit “1” in the expression 4|1 denotes one (1) low order digit that indexes one column in the table.
Let the expression 4|4 denote an “output partition” having a high order output part of four (4) digits and a low order output part of four (4) digits. Line compression is obtained by having a common high order part followed by a sequence of ten (10) low order parts each indexed by the value of the one (1) low order refinement digit.
For example, consider the following two lines from a five (5) digit index decimal logarithm direct lookup table published by Chemical Rubber Publishing Company.
TABLE ONEN012891150060697873567734...9999*03761151061075311311508...37714148
The output of this logarithm table provides a rounded eight (8) digit decimal logarithm partitioned in a 414 output partition. The leading four (4) digits of the logarithm value (i.e., d0. d1 d2 d3) are given by the value d0 and the common three leading fraction digits d1 d2 d3. The digit d0=4 is assumed to be known to the user of the table from the fact that N is a five (5) digit number. In the two lines of the logarithm table shown in TABLE ONE the common three leading fraction digits d1 d2 d3 are either “060” or “061.” The remaining four (4) low order digits d4 d5 d6 d7 refining the output value are obtained from the entries in the columns of the table with the low order refinement digit of the input selecting the particular column.
The table lookup process for looking up the logarithm of the input value N=11501 involves (a) accessing the table values in line “1150” and (b) concatenating the three digits “060” to the four (4) digit low order part “7356” from column “1” and (c) concatenating the fraction to the d0=4 value. The result is the output logarithm value of 4.0607356.
The table lookup process for looking up the logarithm of the input value N=11509 involves (a) accessing the low order table values in line “1150” and (b) recognizing the low order selection “overflow” indicator (i.e., the asterisk) and (c) concatenating the three digits “061” in line “1151” to the four (4) digit low order part “0376” from column “9” and (d) concatenating the fraction to the d0=4 value. The result is the output logarithm value of 4.0610376. The asterisk placed on the value “0376” in column “9” indicates that the three digits “061” from line “1151” are to be used instead of the three digits “060” from the line “1150.”
The input value N=11509 creates an “overflow” exception condition in the low order output part that requires the low order output part “0376” to be concatenated to the high order output part incremented by a carry. In this case the high order output part on line “1150” is “060.” When it is incremented by a carry the value becomes “061” which is the high order part of the next line “1151.” The output “overflow” exception condition is denoted in the lookup table by a leading asterisk included in the low order output part.
The output “overflow” exception condition described above for a published decimal lookup table may also be employed in an analogous binary lookup table (i.e., a table in which the output numbers are printed in binary form). The mathematical principles that are involved are the same. Binary lookup tables are not usually provided in a printed table. This is because the user of a binary lookup table is almost always an “arithmetic logic unit” (ALU) of a computer. Binary lookup tables are usually provided in a computer “read only memory” (ROM). An ALU directly accesses the ROM binary lookup table to obtain desired output values from the table.
Some disadvantages of these prior art low order digit refinement methods are as follows:
(1) Selective concatenation of high and low order digits has a delay due to the dependency of the high order digit selection on the output of the low order digit selection. That is, it must first be determined whether the asterisk symbol that may be output with the low order digits is present or absent.
(2). Neither the high order digits nor the low order digits are available from the initial lookup of the line.
(3) A variety of formatting options for adapting the range of output values are seamlessly employed to achieve greater compression and to reduce the visual clutter on the printed page. An example of a printed page is Page 45 of the book Standard Mathematical Tables, Fourteenth Edition, published by The Chemical Rubber Company of Cleveland, Ohio, shown in Appendix 1. While the reader seamlessly reads the published table, an equivalent hardware implementation can require excessive branching logic and delay in a similar hardware table system that comprises a plurality of ROM tables with a complex selection mechanism.
Accordingly, a need has arisen for a method of compression in a direct lookup table where the output is available with a minimum of conditional post-lookup table logic. A further need has arisen to obtain a direct lookup table compression that is lossless, in order to preserve the integrity of the table lookup values. A further need has arisen for a method for designing the partition of a direct lookup table into a plurality of lookup tables, together with a simple selection mechanism, to enable a desired lookup table of a plurality of lookup tables in order to obtain a desired lookup table value while minimizing power usage and achieving a higher level of lossless compression.
A further need has arisen for an improved apparatus and method for providing a direct lookup table in which the digit values in the direct lookup table are encoded in bits with the bits allocated to parts of the output so as to minimize the total number of bits required to express the values in the direct lookup table thereby achieving greater compression.